This invention relates to an improved cache controlling device and method, and in particular an improved cache controlling device and method to more efficiently determine the least used cache line for eviction from a cache when the cache is full. The invention also relates to an improved bus control device for bridging two data and address buses utilizing a cache controlled by the improved cache controlling device.
In the past, cache controllers have been used to store, organize and retrieve cache lines of data from the memory location of the cache. A particular problem which arises with all caches is selecting which cache line to write back to main memory or "evict" from the cache when the cache is full.
In the best case, the cache controller will send back to main memory a cache line which will not be required in the near future. Otherwise, inefficiencies will arise if the same cache lines are continuously written back and forth between the cache and main memory.
Several different algorithms and principles have been used to try to select which cache line will not be needed in the future and should be evicted from the cache. In general, the least recently used cache line should be evicted as this cache line will likely be the least recently used cache line in the future.
The least recently used cache line can be determined explicitly by tracking the use of the cache lines. However, this tends to be complicated and time consuming in practice. Also, it is only a general principle that the least recently used cache line in the past will continue to be the least recently used cache in the future. It is possible that the least recently used cache line may in fact be the cache line required next.
Therefore, there is an overall decrease in efficiency and an unnecessary increase in the cost of the system if too much effort is expended on determining the least recently used cache line. If a good approximation can be made of a cache line which is one of the least recently used cache lines, there are ever diminishing returns in trying to determine even better approximations or even the least recently used cache line.
Some cache controllers use a pseudo least recently used algorithm (pseudo-LRU) to determine the most likely least recently used cache line. Such a cache controller would determine the last used cache line and select the cache line next to the last used cache line as the likely least used cache line and evict that cache line. While this algorithm is attractive in its simplicity, it suffers from the fact that the cache line immediately next to the last used cache line is likely not the least used cache line because of the way data is stored in a cache. At best, this algorithm can only ensure the last used cache line is not evicted from the cache.
Accordingly, there is a need in the art for an improved pseudo-LRU algorithm which is simple and efficient to implement and which provides a fairly accurate indication of the least recently used cache line. Also, there is a need in the art for an improved pseudo-LRU algorithm which can be used in cases where the cache line sizes are programmable, and therefore the maximum number of cache lines possible in the cache varies. Also, there is a need for an improved pseudo-LRU algorithm which can be used in caches where some cache lines may be considered "locked", meaning that they can not be evicted, and yet a reasonable selection of a least recently used cache line can be made for eviction.